public class Num14 {
    /**
     * 递归大法
     * @param strs
     * @return
     */
//    public String longestCommonPrefix(String[] strs) {
//        if (strs == null || strs.length == 0){
//        return "";
//        }
//        char ch = 0;
//        for (int i = 0; i< strs.length; i++) {
//            String str = strs[i];
//            if (str.length() < 1 || ch != 0 && str.charAt(0) != ch){
//                return "";
//            }
//            if (ch == 0){
//                ch = str.charAt(0);
//            }
//            strs[i] = str.substring(1);
//        }
//        return ch + longestCommonPrefix(strs);
//    }

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0){
            return "";
        }
        return longestCommonPrefix(strs, 0, strs.length-1);
    }

    public String longestCommonPrefix(String[] strs, int start, int end){
        if (start >= end){
            return strs[start];
        }
        int mid = (end - start) / 2 + start;
        return commonPrefix(longestCommonPrefix(strs, start, mid), longestCommonPrefix(strs, mid + 1, end));
    }

    public String commonPrefix(String left, String right){
        StringBuilder res = new StringBuilder();
        for (int i = 0; i<Math.min(left.length(), right.length()); i++){
            if (left.charAt(i) == right.charAt(i)){
                res.append(left.charAt(i));
            } else {
                break;
            }
        }
        return res.toString();
    }

    public static void main(String[] args) {
        Num14 num14 = new Num14();
        System.out.println(num14.longestCommonPrefix(new String[]{"flower","flow","flight"}));
    }

}
